package 回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-22
 */
public class 全排列问题 {
    public static int total = 0;
    //1.非递归
    public static void swap(String[] str, int i, int j) {
        String temp = new String();
        temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    public static void arrange(String[] str, int st, int len) {
        if (st == len - 1) {
            System.out.println(Arrays.asList(str));
            total++;
        } else {
            for (int i = st; i < len; i++) {
                swap(str, st, i);
                arrange(str, st + 1, len);
                swap(str, st, i);
            }
        }

    }

    //2.全排列去重
    public static void wholeSort(char[] arr, int depth) {
        if (depth == arr.length) {
            System.out.println(arr);
        }
        for (int i = depth; i < arr.length; i++) {
            if (hasDup(arr, depth, i)) {
                continue;
            }
            swap(arr, i, depth);
            wholeSort(arr, depth + 1);
            swap(arr, i, depth);
        }
    }

    static boolean[] visited = new boolean[100];
    //3.全排列dfs,剪枝
    public static void wholeSortCut(char[] arr, List list,int length) {
        if (length == arr.length) {
            System.out.println(new ArrayList<>(list));
            return;
        }
        List<Character> level = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (level.contains(arr[i]) || visited[i]) {
                continue;
            }
            list.add(arr[i]);
            level.add(arr[i]);
            visited[i] = true;
            wholeSortCut(arr, list,length+1);
            list.remove(list.size() - 1);
            visited[i] = false;
        }
    }

    //交换
    public static void swap(char[] arr, int start, int end) {
        char temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }    //包含重复

    public static boolean hasDup(char[] arr, int start, int end) {
        for (int i = start; i < end; i++) {
            if (arr[i] == arr[end]) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        wholeSortCut(new char[]{'a', 'b', 'b'}, new ArrayList(),0);
//        wholeSort(new char[]{'a', 'c', 'c'},0);
    }
}
